#include "stdlib.h"
#include "stdio.h"

#ifndef __TRIE_H
#define __TRIE_H

#define DO_PRINT 1;

struct da_state
{
    enum { INITIAL_SIZE=1};
    int base;    /* base array */
    int check;   /* check array */
    
	bool is_final;	 /* flag whether the state can be final state */
	int* label;    /* a list R what is a arc set from current state  */
	
    int label_size;
    int actual_label_size;


    void init()
	{
        base = check = actual_label_size =label_size= 0;
        label = NULL;
		is_final = false;
    }

	void reset()
	{
		delete [] label;
		init();
	}

    int get_label(int* &handle)
	{	
		handle = label;
        return actual_label_size;
    }

    void add_label(int add_label)
    {
        if(label == NULL)
        {
            label_size = INITIAL_SIZE;
            label = new int[INITIAL_SIZE];
        }
        else if( actual_label_size == label_size)
        {
            int pre_size = label_size;
			label_size *= 2;
            int * new_label = new int[label_size];
            for(int i=0; i < pre_size; i++)
			{
				new_label[i] = label[i];
			}
			delete [] label;
			label = new_label;

        }
        label[actual_label_size++] =  add_label;
    }
    
	da_state()
	{
		base = check = actual_label_size =label_size= 0;
        is_final = false;
		label = NULL;
	}


	/* assign construction */
	da_state & operator= (const da_state& o)
	{
		if( this == &o)
			return *this;
		delete [] label; //free old label;
		label = NULL;
		base = o.base;
		check = o.check;
		label_size = o.label_size;
		is_final = o.is_final;
		for(int i = 0; i < o.actual_label_size; i++)
		{
			add_label(o.label[i]);
		}
		return *this;
	}
	
   ~da_state(){ 
		delete [] label; 
	}
};


class Trie
{
public:

    enum { INITIAL_SIZE = 1024, NON_MATCH=-1, BASE_POS=1  };

private:
        da_state *da;	/* an double array */
        int da_size;  /* size of double array */
        int base_pos; /* current base index of the double array */
		int entry_size; /* entry numbers having been added */

public:
		//**************** default construction ******************//
        Trie();

		//**************** deconstruction function ***************// 
		~Trie();

        /**
		 * find out whether string end with 0 is in it.
		 */
        bool retrieve(wchar_t * entry);
		/**
		 * find out whether string with specific length is in it.
		 */
		bool retrieve(wchar_t * entry, int length);

        /**
         * insert a entry into
		 * If the entry have exited, return false;
         * if the entry does not exist, the entry will be appended and return true.
         */
        bool insert(wchar_t * entry);

        /**
         * delete a Token,
		 * If the entry does not exist, delete nothing, just return false.
		 * If the entry exists, delete the entry, then return true.
         */
        //bool remove(wchar_t * entry);

		/**
		 * print state
		 */
		void print_state();

		int entry_number() {
			return entry_size;
		}

		/*
		 * judge wheter current state is a phrase -- the final state of a phrase.
		 */
		bool is_final(int idx) {
			if( idx <= 0 || idx >= da_size) 
				return false;
			return da[idx].is_final; }

		//**** calculate next t = g(s,a), return next state.If NON-MATCH returned, it indicate retireve fail ****//
        int forward(int s, wchar_t a);

		void saveAsDat(const char * path);

		void loadFromDat(const char * path);

    private:
        
		
		
		//**** do doublize the size of double-array iteraly until array size is not small than min ****/
         void re_alloc(int min=-1);
		
		/* find a new base value for index *idx* */
		int x_check(int idx);

        //****************** method for access double array **********************//
        inline void w_base(int index, int v) { da[index].base = v;}
        inline void w_check(int index, int v) { da[index].check = v; }
        inline int r_base(int index) { return da[index].base; }
        inline int r_check(int index) { return da[index].check; }

		//******************* method for dealing with label *********************//
		int label_size(int idx) { return da[idx].actual_label_size; }
		void add_label(int idx, int label){ da[idx].add_label(label); }
		int get_label(int idx, int lable_idx) { return da[idx].label[lable_idx];}

		//******************* method for accessing final flag *******************//
		void set_final(int idx, bool is_final) { da[idx].is_final = is_final; }

		//void set_final(int idx, bool is_finale) { da[idx].is_final = idx; }

};

#endif
